package reviewAlgorithms.search;

import java.util.*;

public class LadderLength {
    public static void main(String[] args) {
        String beginWord = "hit";
        String endWord = "cog";
        String[] words = {"cog"};
        List<String> wordList = Arrays.asList(words);
        int[] state = new int[wordList.size()];
        Arrays.fill(state,1);
        System.out.println(ladderLength(beginWord,endWord,wordList,state));
    }

    private static int ladderLength(String beginWord, String endWord, List<String> wordList, int[] state) {
        if (wordList.size() < 1 || beginWord == null || endWord == null){
            return 0;
        }
        Set<String> set = new HashSet<>();
        Set<String> setTemp = new HashSet<>();
        set.add(beginWord);
        int count = 1;
        while (!set.isEmpty()){
            if (set.contains(endWord)){
                return count;
            }
            for (String str : set) {
                setTemp.addAll(getNext(str,wordList,state));
            }
            if (setTemp.isEmpty()){
                return 0;
            }
            set.clear();
            set.addAll(setTemp);
            setTemp.clear();
            count ++;
        }
        return count;
    }

    private static Set<String> getNext(String str, List<String> wordList, int[] state) {
        Set<String> nextStrs = new HashSet<>();
        for (int i = 0; i < wordList.size(); i++) {
            if (state[i] == 1 && isNestOfStr(str,wordList.get(i))){
                nextStrs.add(wordList.get(i));
                state[i] = 0;
            }
        }
        return nextStrs;
    }

    private static boolean isNestOfStr(String str, String s) {
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) != s.charAt(i)){
                count ++;
            }
            if (count > 1){
                return false;
            }
        }
        return count == 1;
    }
}
